package q91_numDecodings;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {

    List<String> t = new ArrayList<>();
    List<List<String>> ans = new ArrayList<List<String>>();

    public static void main(String[] args) {
        Solution_1 s = new Solution_1();
        String a = "10";
        System.out.println(s.ans);
        System.out.println(s.numDecodings(a));
    }

    /**
     * 错误的方法，应该使用动态规划
     */
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }
        dfs(0, s);
        return ans.size();
    }

    // 问题在于，一次选择添加一个字母，还是两个字母
    private void dfs(int i, String s) {
        // 如果cur到达了数组的长度，也就穷尽了最后一种可能，也就是所有的元素都被判断过了。
        if (i > s.length()) {
            return;
        }else if (i == s.length()){
            ans.add(new ArrayList<String>(t));
            return;
        }


        if (i + 2 <= s.length()){
            // 如果下一个是0，必须添加两个字符
            if (s.charAt(i + 1) == 0){
                t.add(s.substring(i,i + 2));
                dfs(i + 2, s);
            }else if (((s.charAt(i) - '0') * 10 + s.charAt(i + 1) - '0') > 26){
                // 只能一次添加一个数
                t.add(String.valueOf(s.charAt(i)));
                dfs(i + 1, s);

            }else {
                t.add(String.valueOf(s.charAt(i)));
                dfs(i + 1, s);

                t.remove(t.size() - 1);
                t.add(s.substring(i,i + 2));
                dfs(i + 2, s);
            }
        }else {
            t.add(String.valueOf(s.charAt(i)));
            dfs(i + 1, s);
        }

//        if (i + 2 == s.length()){
//
//        }
//        // 先将该节点加入到t中
//        t.add(nums[cur]);
//        dfs(cur + 1, nums);
//
//        //另一种就是该节点没有被加入到t中
//        t.remove(t.size() - 1);
//        dfs(cur + 1, nums);
    }
}
